package com.yuanzhi.train.tree;

/**
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 *
 *
 * 示例 1：
 * 输入：n = 3
 *
 * 输出：5
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：1
 *
 * 提示：
 * 1 <= n <= 19
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/unique-binary-search-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author yuanZhi
 * @since 2022/1/24 9:44
 */
public class NumTrees {
    public static void main(String[] args) {
        System.out.println(numTrees(5));
    }

    /**
     * 假设n个节点的不同二叉树数量为 G(n)
     * 以其中某个数为根节点的二叉树个数为 f(i)
     * 可得： G(n) = f(1) + f(2) + ... + f(i) ... + f(n)
     * 另外，f(i) = 左子树组合方式G(i -1) * 右子树组合方式G(n - i)
     * 所以，G(n) = (G(1-1) * G(n-1)) + (G(2-1) * G(n-2)) + ... + (G(i-1) * G(n-i)) + ... + (G(n-1 - 1) * G(n -n-1)) + (G(n - 1) * G(n - n-0))
     * 即:  G(n) = G(0) * G(n-1) + G(1) * G(n-2) + ... + G(i-1) * G(n-i) + ... + G(n-2) * G(1) + G(n-1 * G(0))
     */
    private static int numTrees(int n) {
        int[] db = new int[n];

        return 0;
    }
}
